\chapter{计数}

\section{计数}

\subsection{分类加法计数原理}

完成一件事有$ n $种不同的方案，其中第$ 1 $种方案有$ m_1 $种不同方法，第$ 2 $种方案有$ m_2 $种不同方法，$ \dots $，第$ n $种方案有$ m_n $种不同方法，那么完成这件事共有$ m_1 + m_2 + \dots + m_n $种不同方法。

\begin{tcolorbox}
	\mybox{Exercise}
	从A地到B地，可以乘火车、汽车、飞机。火车有4班、汽车2班、飞机3班，那么一天中乘坐这些交通工具从A地到B地有多少种不同的走法？
	$$
		4 + 2 + 3 = 9
	$$
\end{tcolorbox}

\vspace{0.5cm}

\subsection{分步乘法计数原理}

完成一件事需要$ n $个步骤，其中第$ 1 $个步骤有$ m_1 $种不同方法，第$ 2 $个步骤有$ m_2 $种不同方法，$ \dots $，第$ n $个步骤有$ m_n $种不同方法，那么完成这件事共有$ m_1 \times m_2 \times \dots m_n $种不同方法。

\begin{tcolorbox}
	\mybox{Exercise}
	一个书架的第1层有4本不同的计算机书，第2层有3本不同的经济书，第3层有2本不同的数学书。从书架的每一层各取一本书，有多少种不同取法？
	$$
		4 \times 3 \times 2 = 24
	$$
\end{tcolorbox}

\newpage

\section{排列}

\subsection{排列（Permutation）}

从$ n $个不同元素中取出$ m\ (m \le n) $ 个元素，按照一定次序排成一列，称为从$ n $个不同元素中取出$ m $个元素的一个排列。

\vspace{-1cm}

\begin{align}
	P_n^m = {n! \over (n-m)!}
\end{align}

例如一共有8个人，A、B、C、D、E、F、G、H。现在有3个奖杯，分别为金牌、银牌和铜牌。将这3个奖牌颁发给8个人中的3个，问颁发奖牌的不同方式总共有几种？\\

很明显这是一个排列的问题，因为把金牌先颁给A，再把银牌颁给B，跟把金牌先颁给B，再把银牌颁给A 这是两种不同的颁奖方式。

\begin{itemize}
	\item 第一步颁发金牌，金牌可以颁发给8个人中的1个，共有8种选择。

	\item 第二步颁发银牌，银牌可以颁发剩下7个人中的1个，共有7种选择。

	\item 第二步颁发铜牌，铜牌可以颁发剩下6个人中的1个，共有6种选择。
\end{itemize}

那么总共的颁奖方式共有$ 8 \times 7 \times 6 = 336 $种。

\begin{tcolorbox}
	\mybox{Exercise}
	用0-9这10个数字可以组成多少个没有重复数字的三位数？\\

	\textbf{方法一}\\
	由于0没有排在百位上，那么百位只能是1-9这9个数字任选1个，有$ P_9^1 $种选法。\\
	对于十位和个位，从余下的9个数字种选2个，有$ P_9^2 $种选法。
	$$
		P_9^1 \times P_9^2 = 9 \times 9 \times 8 = 648
	$$

	\textbf{方法二}\\
	符合条件的三位数可以分为3大类：
	\begin{enumerate}
		\item 每一位数字都不是0的三位数，也就是从1-9中选3个，有$ P_9^3 $种选法。

		\item 个位数字为0，那么需要从剩下9个数字中选2个作为十位和百位，有$ P_9^2 $种选法。

		\item 十位数字为0，那么需要从剩下9个数字中选2个作为个位和百位，有$ P_9^2 $种选法。
	\end{enumerate}
	$$
		P_9^3 + P_9^2 + P_9^2 = 648
	$$

	\textbf{方法三}\\
	利用容斥法。从0-9这10个数字任取3个数字的排列数为$ P_{10}^3 $，其中0在百位上（也就是从1-9中选2个作为十位和个位）的排列数是$ P_9^2 $。
	$$
		P_{10}^3 - P_9^2 = 648
	$$
\end{tcolorbox}

\begin{tcolorbox}
	\mybox{Exercise}
	打印字符串math的全排列。
\end{tcolorbox}

\begin{lstlisting}[language=C, title=全排列]
#include <stdio.h>
#include <string.h>

void swap(char *a, char *b) {
	char temp = *a;
	*a = *b;
	*b = temp;
}

void permutation(char *s, int start, int end) {
	if (start >= end) {
		printf("%s\n", s);
	} else {
		for (int i = start; i < end; i++) {
			swap(s + i, s + start);
			permutation(s, start + 1, end);
			swap(s + i, s + start);
		}
	}
}

int main() {
	char s[] = "math";
	int len = strlen(s);
	permutation(s, 0, len);
	return 0;
}
\end{lstlisting}

\newpage

\section{组合}

\subsection{组合（Combination）}

从$ n $个不同元素中取出$ m\ (m \le n) $ 个元素，称为从$ n $个不同元素中取出$ m $个元素的一个组合。\\

排列与组合的不同点在于，排列与元素的顺序有关，组合与元素的顺序无关。

\vspace{-1cm}

\begin{align}
	C_n^m = {P_n^m \over P_m^m} = {n! \over (n-m)!m!}
\end{align}

\begin{tcolorbox}
	\mybox{Exercise}
	在100件产品中，有98件合格品，2件次品，从这100件产品中任意抽出3件。\\
	(1) 有多少种不同的抽法？
	$$
		C_{100}^3 = {100 \times 99 \times 98 \over 3 \times 2 \times 1} = 161700
	$$

	(2) 抽出的3件中恰好有1件事次品的抽法有多少种？\\
	2件次品抽出1件有$ C_2^1 $种，再从98件合格品种抽出2件合格品有$ C_{98}^2 $种。
	$$
		C_2^1 \times C_{98}^2 = 9506
	$$

	(3) 抽出的3件中至少有1件事次品的抽法有多少种？\\
	\textbf{方法一}\\
	恰好有1件次品有$ C_2^1 \times C_{98}^2 $种，恰好有2件次品有$ C_2^2 \times C_{98}^1 $种。
	$$
		C_2^1 \times C_{98}^2 + C_2^2 \times C_{98}^1 = 9604
	$$

	\textbf{方法二}\\
	利用容斥法。先从100件抽出3件有$ C_{100}^3 $种，其中3件都是合格品有$ C_{98}^3 $种。
	$$
		C_{100}^3 - C_{98}^3 = 9604
	$$
\end{tcolorbox}

\newpage

\section{鸽巢原理}

\subsection{鸽巢原理（Pigeonhole Principle）}

鸽巢原理也称为狄利克雷抽屉原理（Dirichlet Drawer Principle），假设有20只鸽子要飞往19个鸽巢栖息，因此这19个鸽巢中至少有1个鸽巢最少栖息着2只鸽子。

\begin{tcolorbox}
	\mybox{鸽巢原理}\\
	如果k + 1个或者更多的物体放入k个盒子，那么至少有一个盒子包含了2个或更多的物体。
\end{tcolorbox}

在生活中有很多场景都可以用鸽巢原理来解释：

\begin{itemize}
	\item 367个人中一定至少有2个人生日相同。
	\item 27个英文单词中一定至少有2个单词是以同一个字母开头。
\end{itemize}

鸽巢原理指出当物体比盒子多时一定至少有2个物体在同一个盒子里，但是当物体树量超过盒子数量的倍数时，可以得到更多的结论。例如在21个在0 $ \sim $ 9数字中一定有3个是相同的，这是由于21个物体被分配到10个盒子里，那么某个盒子的物体一定多于2个。

\begin{tcolorbox}
	\mybox{广义鸽巢原理}\\
	如果N个物体放入k个盒子，那么至少有一个盒子包含了至少$ \lceil N / k \rceil $个物体。
\end{tcolorbox}

在生活中有很多场景都可以用广义鸽巢原理来解释：

\begin{itemize}
	\item 在100个人中至少有$ \lceil 100 / 12 \rceil = 9 $个人出生在同一个月。
	\item 假设有A、B、C、D、E五个成绩，一个班级至少要有26个学生才能保证至少6个学生得到相同的分数。
\end{itemize}

\begin{tcolorbox}
	\mybox{Exercise}
	(1) 从一副标准的52张牌中必须选多少张牌才能保证选出的牌中至少有3张是同样的花色？\\
	假设用4个盒子存放4种花色的牌，选N张牌后，至少有一个盒子含有至少$ \lceil N / 4 \rceil $张牌。\\
	因此使得$ \lceil N / 4 \rceil \ge 3 $的最小整数$ N = 2 \times 4 + 1 = 9 $\\

	(2) 必须选多少张牌才能保证选出的牌中至少有3张是红桃。\\
	这个场景不适用广义鸽巢原理，因为要保证存在3张红桃，而不是3张同花色的牌。\\
	最坏情况下，在选出第一张红桃之前已经选了所有的其它花色牌共39张，因此为了得到3张红桃，可能需要选42张牌。
\end{tcolorbox}

\newpage

\section{二项式定理}

\subsection{二项式系数（Binomial Coefficient）}

组合数$ C(n, r) $也可写为$ n \choose r $，由于这些数经常出现在$ (x + y)^n $的展开式中作为系数，所以这些数被称为二项式系数。

\vspace{-1cm}

\begin{align*}
	(x + y)^3 & = 1x^3 + 3x^2y + 3xy^2 + 1y^3                                                     \\
	          & = {3 \choose 0} x^3 + {3 \choose 1} x^2y + {3 \choose 2} xy^2 + {3 \choose 3} y^3
\end{align*}

\begin{tcolorbox}
	\mybox{二项式定理}
	\begin{align}
		(x + y)^n & = \sum_{j=0}^{n} {n \choose j}x^{n-j}y^j                                                            \\
		\nonumber
		          & = {n \choose 0} x^n + {n \choose 1} x^{n-1}y + \dots + {n \choose n-1} xy^{n-1} + {n \choose n} y^n
	\end{align}
\end{tcolorbox}

\begin{tcolorbox}
	\mybox{Exercise}
	计算$ (x + y)^{25} $的展开式中$ x^{12}y^{13} $的系数。\\
	$$
		{25 \choose 13} = 5200300
	$$
\end{tcolorbox}

\begin{tcolorbox}
	\mybox{Exercise}
	计算$ (2x - 3y)^{25} $的展开式中$ x^{12}y^{13} $的系数。
	\begin{align*}
		(2x + (-3y))^{25} & = \sum_{j=0}^{25} {25 \choose j} (2x)^{25-j} (-3y)^j                \\
		                  & = \sum_{j=0}^{25} {25 \choose j} (2)^{25-j} (x)^{25-j} (-3)^j (y)^j
	\end{align*}
	$ x^{12}y^{13} $的系数为$ {25 \choose 13} \cdot 2^{12} \cdot (-3)^{13} $
\end{tcolorbox}

\begin{tcolorbox}
	\mybox{推论1}
	\begin{align}
		\sum_{j=0}^{n} {n \choose j} = 2^n
	\end{align}
	\mybox{证明}
	\begin{align*}
		2^n & = (1 + 1)^n                                \\
		    & = \sum_{j=0}^{n} {n \choose j} 1^{n-j} 1^j \\
		    & = \sum_{j=0}^{n} {n \choose j}
	\end{align*}
\end{tcolorbox}

\begin{tcolorbox}
	\mybox{推论2}
	\begin{align}
		\sum_{j=0}^{n} {n \choose j} (-1)^j = 0
	\end{align}
	\mybox{证明}
	\begin{align*}
		0 & = (1 - 1)^n                                   \\
		  & = \sum_{j=0}^{n} {n \choose j} 1^{n-j} (-1)^j \\
		  & = \sum_{j=0}^{n} {n \choose j} (-1)^j
	\end{align*}
\end{tcolorbox}

\begin{tcolorbox}
	\mybox{推论3}
	\begin{align}
		\sum_{j=0}^{n} {n \choose j} (2)^j = 3^n
	\end{align}
	\mybox{证明}
	\begin{align*}
		3^n & = (1 + 2)^n                                \\
		    & = \sum_{j=0}^{n} {n \choose j} 1^{n-j} 2^j \\
		    & = \sum_{j=0}^{n} {n \choose j} (2)^j
	\end{align*}
\end{tcolorbox}

\vspace{0.5cm}

\subsection{帕斯卡恒等式（Pascal's Identity）}

\begin{tcolorbox}
	\mybox{帕斯卡恒等式}
	\begin{align}
		{n+1 \choose k} = {n \choose k-1} + {n \choose k}
	\end{align}
	\mybox{证明}\\
	假设$ n + 1 \choose k $表示在长度为$ n + 1 $的二进制串中正好有$ k $个1的二进制串数量，满足条件的二进制串可以分成两组：
	\begin{itemize}
		\item 以1开头的二进制串：因为1是开头，所以剩余部分中包含$ k - 1 $个1，即$ n \choose k - 1 $。
		\item 以0开头的二进制串：因为0是开头，所以剩余部分中包含$ k $个1，即$ n \choose k $。
	\end{itemize}
\end{tcolorbox}

\vspace{0.5cm}

\subsection{范德蒙德恒等式（Vandermonde's Identity）}

\begin{tcolorbox}
	\mybox{范德蒙德恒等式}
	\begin{align}
		{m+n \choose r} = \sum_{k=0}^r {m \choose r-k} {n \choose k}
	\end{align}
	\mybox{证明}\\
	假设$ m+n \choose r $表示从集合A（m个元素）和集合B（n个元素）中选取r个元素。可以从集合A中取$ r - k $个元素，再从集合B中取$ k $个元素，一共有$ {m \choose r-k} {n \choose k} $种取法，其中$ 0 \le k \le r $。最后将所有满足条件的$ k $进行累加，即可得到范德蒙德恒等式。
\end{tcolorbox}

\newpage

\section{可重复的排列组合}

\subsection{可重复的排列}

在许多计数问题中，元素可以被重复使用，例如一个字母或数字可以在车牌号中重复出现。\\

当元素允许重复时，使用乘法法则可以很容易地计算排列数。具有n个元素的集合允许重复的r排列数为$ n^r $。

\begin{tcolorbox}
	\mybox{Exercise}
	用大写字母可以构成多少个长度为10的字符串？
	$$
		26^{10}
	$$
\end{tcolorbox}

\vspace{0.5cm}

\subsection{可重复的组合}

当元素允许重复时，从n个元素的集合选取r个元素的组合数为

\vspace{-1cm}

\begin{align}
	C(n+r-1, r) = {n+r-1 \choose r}
\end{align}

\begin{tcolorbox}
	\mybox{Exercise}
	从包含1元、2元、5元、10元、20元、50元和100元的钱袋中选取5张有多少种不同的取法？
	\begin{align*}
		C(7+5-1, 5) = {11 \choose 5} = 462
	\end{align*}
\end{tcolorbox}

\vspace{0.5cm}

\subsection{不可区别物体的排列}

在计数问题中，某些元素可能是没有区别的，这种情况必须要避免重复计数。\\

假设有$ n_1 $个相同元素1、$ n_2 $个相同元素2、$ \dots $、$ n_k $个相同元素k，那么n个元素的不同排列数为

\vspace{-1cm}

\begin{align}
	n! \over n_1! \cdot n_2! \cdot \dots \cdot n_k!
\end{align}

\begin{tcolorbox}
	\mybox{Exercise}
	由4个A、3个B、7个C和1个D能组成多少个不同的字符串？
	\begin{align*}
		15! \over 4! \cdot 3! \cdot 7! \cdot 1!
	\end{align*}
\end{tcolorbox}

\newpage